#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=5e5+1000;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar();while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f;}
LL tot=0;
LL a[maxn],root[maxn];
struct Tree{
    LL lson,rson,sum;
}tree[maxn<<5];
void push_up(LL p){
    tree[p].sum=tree[tree[p].lson].sum+tree[tree[p].rson].sum;
}
LL update(LL pre,LL l,LL r,LL k,LL val){
    LL rt=++tot;
    ///tree[rt]=tree[pre];
    tree[rt].sum=tree[pre].sum;
    tree[rt].lson=tree[pre].lson;
    tree[rt].rson=tree[pre].rson;
    if(l==r){
        tree[rt].sum+=val;
        return rt;
    }
    LL mid=(l+r)>>1;
    if(k<=mid){
        tree[rt].lson=update(tree[pre].lson,l,mid,k,val);
    }
    else tree[rt].rson=update(tree[pre].rson,mid+1,r,k,val);
    push_up(rt);
    return rt;
}
LL query(LL now,LL pre,LL l,LL r,LL x){
    LL sum=tree[now].sum-tree[pre].sum;
    if(sum<=x) return -1;
    if(l==r) return l;
    LL mid=(l+r)>>1;
    LL ans=-1;
    if(tree[tree[now].lson].sum-tree[tree[pre].lson].sum>x){
        ans=query(tree[now].lson,tree[pre].lson,l,mid,x);
        if(ans>0){
            return ans;
        }
    }
    if(tree[tree[now].rson].sum-tree[tree[pre].rson].sum>x){
        ans=query(tree[now].rson,tree[pre].rson,mid+1,r,x);
        if(ans>0){
            return ans;
        }
    }
    return ans;
}
int main(void)
{
  LL n,m;n=read();m=read();
  for(LL i=1;i<=n;i++) a[i]=read();
  for(LL i=1;i<=n;i++){
    root[i]=update(root[i-1],1,n,a[i],1);
  }
  while(m--){
    LL l,r;l=read();r=read();
    LL k=(r-l+1)/2;
    LL ans=query(root[r],root[l-1],1,n,k);
    if(ans==-1){
        puts("1");
    }
    else{

    }
  }
return 0;
}
